package com.heima.leetcode.practice;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 67. 二进制求和
 * @date 2025/5/13 20:42
 */
public class E67 {

    /**
     * 思路一：补全
     *
     * @param a 二进制字符串a
     * @param b 二进制字符串b
     * @return 二进制结果
     */
    public String addBinary1(String a, String b) {
        int lengthA = a.length(), lengthB = b.length();
        StringBuilder builder = new StringBuilder();
        builder.append("0".repeat(Math.abs(lengthB - lengthA)));
        if (lengthA < lengthB) {
            builder.append(a);
            a = builder.toString();
        } else {
            builder.append(b);
            b = builder.toString();
        }
        char[] str1 = a.toCharArray();
        char[] str2 = b.toCharArray();
        int carry = 0;
        builder.setLength(0);
        for (int i = str1.length - 1; i >= 0; i--) {
            int sum = str1[i] - '0' + str2[i] - '0' + carry;
            builder.append(sum % 2);
            carry = sum / 2;
        }
        if (carry == 1) builder.append(carry);
        return builder.reverse().toString();
    }

    /**
     * 思路二：位运算优化和边遍历边处理
     *
     * @param a 二进制字符串a
     * @param b 二进制字符串b
     * @return 二进制结果
     */
    public String addBinary(String a, String b) {
        int lengthA = a.length(), lengthB = b.length();
        StringBuilder builder = new StringBuilder();
        char[] str1 = a.toCharArray();
        char[] str2 = b.toCharArray();
        int carry = 0, index1 = lengthA - 1, index2 = lengthB - 1;
        while (index1 >= 0 || index2 >= 0) {
            int num1 = index1 < 0 ? 0 : str1[index1] - '0';
            int num2 = index2 < 0 ? 0 : str2[index2] - '0';
            int sum = num1 + num2 + carry;
            builder.append(sum & 1);
            carry = sum >> 1;
            index1--;
            index2--;
        }
        if (carry == 1) builder.append(carry);
        return builder.reverse().toString();
    }
}
